package com.practice.niuke.new_direct_basics.class13;

import java.util.ArrayList;
import java.util.List;

/**
 * 派对的最大快乐值
 * 员工信息的定义如下:
 * class Employee {
 * public int happy; // 这名员工可以带来的快乐值
 * List<Employee> subordinates; // 这名员工有哪些直接下级
 * } 公
 * 司的每个员工都符合 Employee 类的描述。 整个公司的人员结构可以看作是一棵标准的、 没有环的
 * 多叉树。 树的头节点是公司唯一的老板。 除老板之外的每个员工都有唯一的直接上级。 叶节点是没有
 * 任何下属的基层员工(subordinates列表为空)， 除基层员工外， 每个员工都有一个或多个直接下级。
 * 这个公司现在要办party， 你可以决定哪些员工来， 哪些员工不来。 但是要遵循如下规则。
 * 1.如果某个员工来了， 那么这个员工的所有直接下级都不能来
 * 2.派对的整体快乐值是所有到场员工快乐值的累 加
 * 3.你的目标是让派对的整体快乐值尽量大
 * 给定一棵多叉树的头节点boss， 请返回派对的最大快乐值。
 */
public class Code03_MaxHappy {

    public static int maxHappy(int[][] matrix) {
        int[][] dp = new int[matrix.length][2];
        boolean[] visited = new boolean[matrix.length];
        int root = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (i == matrix[i][0]) {
                root = i;
            }
        }
        process(matrix, dp, visited, root);
        return Math.max(dp[root][0], dp[root][1]);
    }

    public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root) {
        visited[root] = true;
        dp[root][1] = matrix[root][1];
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == root && !visited[i]) {
                process(matrix, dp, visited, i);
                dp[root][1] += dp[i][0];
                dp[root][0] += Math.max(dp[i][1], dp[i][0]);
            }
        }
    }

    /**
     * 多叉树的节点
     */
    public static class Node {
        /**
         * 当前节点的快乐度
         */
        public int happy;
        /**
         * 当前几点的子节点列表
         */
        public List<Node> nexts;

        public Node(int happy) {
            this.happy = happy;
            this.nexts = new ArrayList<>();
        }

        public Node(int happy, List<Node> nexts) {
            this.happy = happy;
            this.nexts = nexts;
        }
    }

    /**
     * 获得整棵树最大快乐度的主流程函数
     *
     * @param head head
     * @return int
     */
    public static int maxHappy(Node head) {
        InfoNew info = processNew(head);
        return Math.max(info.headNo, info.headNo);
    }

    /**
     * 信息体（对于任意一棵树）
     */
    public static class InfoNew {
        /**
         * 头节点不来的情况下获得的最大快了值
         */
        public int headNo;
        /**
         * 头节点来的情况下获得的最大快乐值
         */
        public int headYes;

        public InfoNew(int headNo, int headYes) {
            this.headNo = headNo;
            this.headYes = headYes;
        }
    }

    /**
     * 以x为头的子树的递归流程，返回要求的所有信息，Info
     *
     * @param x x
     * @return InfoNew
     */
    public static InfoNew processNew(Node x) {
        if (x.nexts.isEmpty()) {// x为最基层的员工， base case
            return new InfoNew(0, x.happy);
        }
        // x有下级节点时：

        // x节点不来的初始值
        int headNo = 0;
        // x节点来的初始值
        int headYex = x.happy;
        // 处理每一个下级节点求得最终的headNo和headYex
        for (Node everyNext : x.nexts) {
            InfoNew cur = processNew(everyNext);
            // 每个节点来的情况下，只能累加 下级节点不来时的快乐值
            headYex += cur.headNo;
            // 每个节点来的情况下，能累加 下级节点不来或者来时的最大值
            headNo += Math.max(cur.headNo, cur.headYes);
        }

        return new InfoNew(headNo, headYex);
    }


    public static class Employee {
        public int happy; // 这名员工可以带来的快乐值
        public List<Employee> nexts; // 这名员工有哪些直接下级
    }


    public static int maxHappy(Employee boss) {
        Info headInfo = process(boss);
        return Math.max(headInfo.laiMaxHappy, headInfo.buMaxHappy);
    }

    public static class Info {
        public int laiMaxHappy;
        public int buMaxHappy;

        public Info(int lai, int bu) {
            laiMaxHappy = lai;
            buMaxHappy = bu;
        }
    }

    public static Info process(Employee x) {
        if (x.nexts.isEmpty()) { // x是基层员工的时候
            return new Info(x.happy, 0);
        }
        int lai = x.happy; // x来的情况下，整棵树最大收益
        int bu = 0; // x不来的情况下，整棵树最大收益
        for (Employee next : x.nexts) {
            Info nextInfo = process(next);
            lai += nextInfo.buMaxHappy;
            bu += Math.max(nextInfo.laiMaxHappy, nextInfo.buMaxHappy);
        }
        return new Info(lai, bu);
    }


    public static void main(String[] args) {
        int[][] matrix = {{1, 8}, {1, 9}, {1, 10}};
        System.out.println(maxHappy(matrix));
    }
}
